package com.example.leetcode.double_pointer;

import java.util.HashMap;
import java.util.Map;

class Solution_76 {
    private Map<Character, Integer> origin;
    private Map<Character, Integer> count;

    public static void main(String[] args) {
        Solution_76 solution_76 = new Solution_76();
        String s1 = "ADOBECODEBANC";
        String s2 = "ABC";
        solution_76.minWindow(s1, s2);

    }

    public String minWindow(String s, String t) {
        //窗口中包含的字符以及数量
        count = new HashMap();
        //统计字符串t的字符和数量
        origin = new HashMap();
        // 窗口左边界
        int left = 0;
        // 窗口右边界
        int right = 0;
        // 窗口的长度
        int len = Integer.MAX_VALUE;
        // 最终的左边界
        int ansLeft = -1;
        // 最终的右边界
        int ansRight = -1;
        int length = s.length();

        //1、统计字符串t中的各个字符的个数,统计结果放到origin，Map中
        for (char c : t.toCharArray()) {
            origin.put(c,origin.getOrDefault(c,0) + 1);
        }
        //2、遍历字符串s
        while(right < length){
            //获取右边界的字符
            char c = s.charAt(right);

            //3、判断Map->origin中是否包含当前字符c
            if(origin.containsKey(c)){
                //当前窗口中,涵盖字符串t中的一个字符
                // 把当前字符放到count中
                count.put(c,count.getOrDefault(c,0) + 1);
            }
            //4、检查当前窗口是否包含字符串t中，所有的字符
            while(check() && left <= right){
                //5、判断窗口还能不能继续缩小
                if(right - left + 1 < len){
                    // 窗口还能缩小
                    len = right - left + 1;
                    ansLeft = left;
                    ansRight = right + 1;
                }
                // 6、如果origin中包含当前元素
                // 窗口缩小，需要从count中移除left处的元素
                if(origin.containsKey(s.charAt(left))){
                    count.put(s.charAt(left),count.getOrDefault(s.charAt(left),0) - 1);
                }
                // 窗口缩小
                left++;
            }
            // 记得右移右边界，然后继续寻找
            right++;
        }
        // 7、如果答案的右边界没经过更新，说明没有找到符合要求的值，就直接返回空的好了，否则的话，就返回子字符串
        return ansRight == -1 ? "" : s.substring(ansLeft, ansRight);
    }
    //检查当前窗口是否包含字符串t中，所有的字符
    private boolean check(){
        //遍历t的统计结果
        for(Map.Entry<Character, Integer> entry : origin.entrySet()){
            if(count.getOrDefault(entry.getKey(),0) < entry.getValue()){
                return false;
            }
        }
        return true;
    }
}